package com.zjj.learn.algorithmPlus.segment2.binaryTree;

import java.util.LinkedList;

/**
 * @author zjj_admin
 */
public class BinaryTreeTraversal {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(new TreeNode(new TreeNode(4), 2, new TreeNode(6)),
                1,
                new TreeNode(null, 3, new TreeNode(5)));
        //前序遍历
        preOrder(root);
        System.out.println();
        inOrder(root);
        System.out.println();

        //后续遍历
        postOrder(root);

        int maxDepth2 = maxDepth2(root);
        System.out.println("maxDepth2 = " + maxDepth2);
    }

    /**
     * 前序遍历，继续递归实现
     *
     * @param root
     */
    static void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + "\t");
        preOrder(root.left);
        preOrder(root.right);
    }


    /**
     * 中序遍历
     *
     * @param root
     */
    static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + "\t");
        inOrder(root.right);
    }


    /**
     * 后续遍历
     *
     * @param root
     */
    static void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + "\t");
    }

    /**
     * 使用递归的思想获取二叉树的最大深度
     * 后续遍历的思想
     *
     * @param root
     * @return
     */
    static int maxDepth1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMax = maxDepth1(root.left);
        int rightMax = maxDepth1(root.right);
        return Math.max(leftMax, rightMax) + 1;
    }


    /**
     * 使用迭代的思想求最大深度
     * 后续遍历
     *
     * @param root
     * @return
     */
    static int maxDepth2(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList();
        int res = 0;
        TreeNode curr = root;
        TreeNode pop = null;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                int size = stack.size();
                res = Math.max(res, size);
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null || peek.right == pop) {
                    //弹栈
                    pop = stack.pop();
                } else {
                    curr = peek.right;
                }
            }
        }
        return res;
    }

}
